class Solution {
    public String minWindow(String s, String t) {
        int[] amp=new int[128];
        for(int i=0;i<t.length();i++){
            amp[t.charAt(i)]++;
        }
        int count=t.length();
        int len=s.length();
        int end=0;
        int head=0;
        int d=Integer.MAX_VALUE;
        int begin=0;
        while(end<len){
            if((amp[s.charAt(end++)]--) > 0){
                count--;
            }
            while(count==0){
                if(end-begin<d){
                    d=end-begin;
                    head=begin;
                }
                if(amp[s.charAt(begin++)]++ == 0){
                    count++;
                }
            }
        }
        return  d == Integer.MAX_VALUE ? "" : s.substring(head,head+d);
    }
}















import java.util.*;
public class Solution {
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        int[] map=new int[128];
        for(int i=0;i<T.length();i++){
            map[T.charAt(i)]++;
        }
        int begin=0;
        int end=0;
        int count=T.length();
        int d=Integer.MAX_VALUE;
        int head=0;
        int len=S.length();
        while(end<len){
            if(map[S.charAt(end++)]-->0){
                count--;
            }
            while(count==0){
                if(end-begin<d){
                    d=end-(head=begin);
                }
                if(map[S.charAt(begin++)]++ == 0){
                    count++;
                }
            }
        }
        return d==Integer.MAX_VALUE?"":S.substring(head,head+d);
    }
}







import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        int len=num.length;
        int max=0;
        ArrayList<Integer> arr=new ArrayList<Integer>();
        if(size==0){
            return arr;
        }
        for(int i=0;i<=len-size;i++){
            max=0;
            for(int j=i;j<size+i;j++){
                max=Math.max(max,num[j]);
            }
            arr.add(max);
        }
        return arr;
    }
}











class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len=nums.length;
        int[] arr1=new int[len];
        int[] arr2=new int[len];
        for(int i=0;i<len;i++){
            if(i%k==0){
                arr1[i]=nums[i];
            }else{
                arr1[i]=Math.max(arr1[i-1],nums[i]);
            }
        }
        for(int i=len-1;i>=0;i--){
            if(i==len-1||(i+1)%k==0){
                arr2[i]=nums[i];
            }else{
                arr2[i]=Math.max(arr2[i+1],nums[i]);
            }
        }
        int[] arr=new int[len+1-k];
        for(int i=0;i<=len-k;i++){
            arr[i]=Math.max(arr1[i+k-1],arr2[i]);
        }
        return arr;
    }
}











import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int left=0;
        int right=array.length-1;
        ArrayList<Integer> arr=new ArrayList<Integer>();
        while(left<right){
            int mid=array[left]+array[right];
            if(mid>sum){
                right--;
            }else if(mid<sum){
                left++;
            }else if(mid==sum){
                arr.add(array[left]);
                arr.add(array[right]);
                break;
            }
        }
        return arr;
    }
}









class Solution {
    public int countTriplets(int[] arr) {
        int len=arr.length;
        int[] ans=new int[len+1];
        for(int i=0;i<len;i++){
            ans[i+1]=ans[i]^arr[i];
        }
        int count=0;
        for(int i=0;i<len;i++){
            for(int k=i+1;k<len;k++){
                if(ans[i]==ans[k+1]){
                    count+=k-i;
                }
            }
        }
        return count;
    }
}










class Solution {
    public String sortString(String s) {
        int[] arr=new int[26];
        for(int i=0;i<s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        StringBuffer sb=new StringBuffer();
        while(sb.length()<s.length()){
            for(int i=0;i<26;i++){
                if(arr[i]>0){
                    sb.append((char) (i+'a'));
                    arr[i]--;
                }
            }
            for(int i=25;i>=0;i--){
                if(arr[i]>0){
                    sb.append((char) (i+'a'));
                    arr[i]--;
                }
            }
        }
        return sb.toString();
    }
}














class MovingAverage {
    double[] arr;
    int size;
    double count=0;
    int x=0;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.arr=new double[size];
        this.size=size;
        this.count=0;
        this.x=0;
    }

    public double next(int val) {
        count=count-arr[x%size]+val;
        arr[x%size]=val;
        x++;
        return count/(size>x?x:size);
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */













class Solution {
    public int[] countBits(int n) {
        int[] arr=new int[n+1];
        int count=0;
        for(int i=0;i<=n;i++){
            int x=i;
            count=0;
            while(x!=0){
                if((x&1) != 0 ){
                    count++;
                }
                x>>=1;
            }
            arr[i]=count;
        }
        return arr;
    }
}











class Solution {
    int[][] arr;
    int n;
    List<List<Integer>> head=new ArrayList<List<Integer>>();
    List<Integer> cur=new ArrayList<Integer>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        arr=graph;
        n=graph.length;
        cur.add(0);
        dfs(0);
        return head;
    }
    public void dfs(int x){
        if(x==n-1){
            head.add(new ArrayList<>(cur));
            return;
        }
        for(int next:arr[x]){
            cur.add(next);
            dfs(next);
            cur.remove(cur.size()-1);
        }
    }
}













class Solution {
    public int singleNumber(int[] nums) {
        int index=0;
        boolean bool=true;;
        for(int i=0;i<nums.length;i++){
            bool=true;
            for(int j=0;j<nums.length;j++){
                if(nums[i]==nums[j]&&i!=j){
                    bool=false;
                    break;
                }
            }
            if(bool){
                return nums[i];
            }
        }
        return 0;
    }
}










class Solution {
    List<Integer> cur=new ArrayList<Integer>();
    List<List<Integer>> head=new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets(int[] nums) {
        int len=nums.length;
        for(int i=0;i<(1<<len);i++){
            cur.clear();
            for(int j=0;j<len;j++){
                if((i & (1<<j))!=0){
                    cur.add(nums[j]);
                }
            }
            head.add(new ArrayList<Integer>(cur));
        }
        return head;
    }
}










class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int max=0;
        int sum=0;
        for(int[] res:rectangles){
            int len=Math.min(res[0],res[1]);
            if(len>max){
                max=len;
                sum=1;
            }else if(len==max){
                sum++;
            }
        }
        return sum;
    }
}
















class Base{

    public Base(String s){

        System.out.print("B");

    }

}

public class prog extends Base{

    public prog(String s) {
        super(s);

        System.out.print("D");

    }

    public static void main(String[] args){

        new prog("C");

    }

}